package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/3/20 10:10 AM
 */
public class 查找当前位置向前向后的第一个最大值_01 {


    public void findPreNextFirstMax(int[] nums) {

        if (nums == null) {

            return;
        }

        int[] leftFirstMaxs = new int[nums.length];
        int[] rightFirstMaxs = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {

            leftFirstMaxs[i] = rightFirstMaxs[i] = -1;
        }

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {

            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {

                // 5,2,1,3,4,6
                rightFirstMaxs[stack.pop()] = i;
            }

            if (!stack.isEmpty()) {

                leftFirstMaxs[i] = stack.peek();
            }
            stack.push(i);
        }

        System.out.println(Arrays.toString(leftFirstMaxs));
        System.out.println(Arrays.toString(rightFirstMaxs));

    }


}
